package bfs;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Main
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description:
 * @date 2021/5/12
 **/
public class Main {

    public static void main(String[] args) {

        String beginWord = "cet", endWord = "ism";
        String[] words = {"kid", "tag", "pup", "ail", "tun", "woo", "erg",
                "luz", "brr", "gay", "sip", "kay", "per", "val", "mes",
                "ohs", "now", "boa", "cet", "pal", "bar", "die", "war",
                "hay", "eco", "pub", "lob", "rue", "fry", "lit", "rex",
                "jan", "cot", "bid", "ali", "pay", "col", "gum", "ger",
                "row", "won", "dan", "rum", "fad", "tut", "sag", "yip",
                "sui", "ark", "has", "zip", "fez", "own", "ump", "dis",
                "ads", "max", "jaw", "out", "btu", "ana", "gap", "cry",
                "led", "abe", "box", "ore", "pig", "fie", "toy", "fat",
                "cal", "lie", "noh", "sew", "ono", "tam", "flu", "mgm",
                "ply", "awe", "pry", "tit", "tie", "yet", "too", "tax",
                "jim", "san", "pan", "map", "ski", "ova", "wed", "non",
                "wac", "nut", "why", "bye", "lye", "oct", "old", "fin",
                "feb", "chi", "sap", "owl", "log", "tod", "dot", "bow", "fob", "for", "joe", "ivy", "fan", "age", "fax", "hip", "jib", "mel", "hus", "sob", "ifs", "tab", "ara", "dab", "jag", "jar", "arm", "lot", "tom", "sax", "tex", "yum", "pei", "wen", "wry", "ire", "irk", "far", "mew", "wit", "doe", "gas", "rte", "ian", "pot", "ask", "wag", "hag", "amy", "nag", "ron", "soy", "gin", "don", "tug", "fay", "vic", "boo", "nam", "ave", "buy", "sop", "but", "orb", "fen", "paw", "his", "sub", "bob", "yea", "oft", "inn", "rod", "yam", "pew", "web", "hod", "hun", "gyp", "wei", "wis", "rob", "gad", "pie", "mon", "dog", "bib", "rub", "ere", "dig", "era", "cat", "fox", "bee", "mod", "day", "apr", "vie", "nev", "jam", "pam", "new", "aye", "ani", "and", "ibm", "yap", "can", "pyx", "tar", "kin", "fog", "hum", "pip", "cup", "dye", "lyx", "jog", "nun", "par", "wan", "fey", "bus", "oak", "bad", "ats", "set", "qom", "vat", "eat", "pus", "rev", "axe", "ion", "six", "ila", "lao", "mom", "mas", "pro", "few", "opt", "poe", "art", "ash", "oar", "cap", "lop", "may", "shy", "rid", "bat", "sum", "rim", "fee", "bmw", "sky", "maj", "hue", "thy", "ava", "rap", "den", "fla", "auk", "cox", "ibo", "hey", "saw", "vim", "sec", "ltd", "you", "its", "tat", "dew", "eva", "tog", "ram", "let", "see", "zit", "maw", "nix", "ate", "gig", "rep", "owe", "ind", "hog", "eve", "sam", "zoo", "any", "dow", "cod", "bed", "vet", "ham", "sis", "hex", "via", "fir", "nod", "mao", "aug", "mum", "hoe", "bah", "hal", "keg", "hew", "zed", "tow", "gog", "ass", "dem", "who", "bet", "gos", "son", "ear", "spy", "kit", "boy", "due", "sen", "oaf", "mix", "hep", "fur", "ada", "bin", "nil", "mia", "ewe", "hit", "fix", "sad", "rib", "eye", "hop", "haw", "wax", "mid", "tad", "ken", "wad", "rye", "pap", "bog", "gut", "ito", "woe", "our", "ado", "sin", "mad", "ray", "hon", "roy", "dip", "hen", "iva", "lug", "asp", "hui", "yak", "bay", "poi", "yep", "bun", "try", "lad", "elm", "nat", "wyo", "gym", "dug", "toe", "dee", "wig", "sly", "rip", "geo", "cog", "pas", "zen", "odd", "nan", "lay", "pod", "fit", "hem", "joy", "bum", "rio", "yon", "dec", "leg", "put", "sue", "dim", "pet", "yaw", "nub", "bit", "bur", "sid", "sun", "oil", "red", "doc", "moe", "caw", "eel", "dix", "cub", "end", "gem", "off", "yew", "hug", "pop", "tub", "sgt", "lid", "pun", "ton", "sol", "din", "yup", "jab", "pea", "bug", "gag", "mil", "jig", "hub", "low", "did", "tin", "get", "gte", "sox", "lei", "mig", "fig", "lon", "use", "ban", "flo", "nov", "jut", "bag", "mir", "sty", "lap", "two", "ins", "con", "ant", "net", "tux", "ode", "stu", "mug", "cad", "nap", "gun", "fop", "tot", "sow", "sal", "sic", "ted", "wot", "del", "imp", "cob", "way", "ann", "tan", "mci", "job", "wet", "ism", "err", "him", "all", "pad", "hah", "hie", "aim", "ike", "jed", "ego", "mac", "baa", "min", "com", "ill", "was", "cab", "ago", "ina", "big", "ilk", "gal", "tap", "duh", "ola", "ran", "lab", "top", "gob", "hot", "ora", "tia", "kip", "han", "met", "hut", "she", "sac", "fed", "goo", "tee", "ell", "not", "act", "gil", "rut", "ala", "ape", "rig", "cid", "god", "duo", "lin", "aid", "gel", "awl", "lag", "elf", "liz", "ref", "aha", "fib", "oho", "tho", "her", "nor", "ace", "adz", "fun", "ned", "coo", "win", "tao", "coy", "van", "man", "pit", "guy", "foe", "hid", "mai", "sup", "jay", "hob", "mow", "jot", "are", "pol", "arc", "lax", "aft", "alb", "len", "air", "pug", "pox", "vow", "got", "meg", "zoe", "amp", "ale", "bud", "gee", "pin", "dun", "pat", "ten", "mob"};

        List<String> wordList = Arrays.asList(words);
        List<List<String>> ans = Solution.findLadders(beginWord, endWord, wordList);

        for (List<String> list : ans) {
            StringBuilder builder = new StringBuilder("[ ");
            for (String str : list) {
                builder.append(str).append(" ; ");
            }
            builder.append(" ]");
            System.out.println(builder);
        }
    }

    static class Solution {

        private static int min = Integer.MAX_VALUE;

        public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            List<List<String>> ans = new ArrayList<>();
            if (!wordList.contains(endWord)) {
                return ans;
            }
            // 得到每个单词相邻的单词
            Map<String, List<String>> map = new LinkedHashMap<>();
            findEachWordNeighbors(beginWord, map, wordList);

            for (String key : map.keySet()) {
                List<String> list = map.get(key);
                StringBuilder builder = new StringBuilder("[ ");
                for (String str : list) {
                    builder.append(str).append(" ; ");
                }
                builder.append(" ]");
                System.out.println(key + " ==> " + builder);
            }
            if (map.size() == 0) return ans;
            Set<String> visited = new HashSet<>();
            List<String> list = new ArrayList<>();
            dfs(beginWord, endWord, map, ans, visited, list, 1);
            ans = filter(ans);
            return ans;
        }

        private static List<List<String>> filter(List<List<String>> ans) {
            int minSize = Integer.MAX_VALUE;
            for (List<String> list : ans) {
                if (list.size() <= minSize) {
                    minSize = list.size();
                }
            }
            final int finalMinSize = minSize;
            List<List<String>> finalAns = ans.stream().filter(list -> list.size() > finalMinSize ? false : true).collect(Collectors.toList());
            return finalAns;
        }

        private static void dfs(String beginWord, String endWord, Map<String, List<String>> map, List<List<String>> ans,

                                Set<String> visited, List<String> list, int step) {
            if (step > min) return;
            if (beginWord.equals(endWord)) {
                list.add(endWord);
                min = Math.min(min, step);
                ans.add(new ArrayList<>(list));
                list.remove(endWord);
                return;
            }
            if (visited.contains(beginWord)) return;
            visited.add(beginWord);
            list.add(beginWord);
            List<String> neighbors = map.get(beginWord);
            if (neighbors != null && neighbors.size() != 0) {
                for (String word : neighbors) {
                    dfs(word, endWord, map, ans, visited, list, step + 1);
                }
            }
            visited.remove(beginWord);
            list.remove(beginWord);
        }

        private static void findEachWordNeighbors(String beginWord, Map<String, List<String>> map, List<String> wordList) {
            if (!wordList.contains(beginWord)) {
                findWordNeighbors(beginWord, map, wordList);
            }
            for (String word : wordList) {
                findWordNeighbors(word, map, wordList);
            }
        }

        private static boolean judgeTwoWordsIsNeighbor(String word, String tmp, List<String> wordList) {
            if (!wordList.contains(tmp)) return false;
            if (word.length() != tmp.length()) return false;
            int[] countWordChars = new int[26];
            int[] countTmpChars = new int[26];
            for (int i = 0; i < word.length(); ++i) {
                int index1 = word.charAt(i) - 'a';
                countWordChars[index1] += 1;
                int index2 = tmp.charAt(i) - 'a';
                countTmpChars[index2] += 1;
            }
            for (int j = 0; j < countWordChars.length; ++j) {
                if (countWordChars[j] >= countTmpChars[j]) {
                    countWordChars[j] -= countTmpChars[j];
                    countTmpChars[j] = 0;
                } else {
                    countTmpChars[j] -= countWordChars[j];
                    countWordChars[j] = 0;
                }
            }
            int countWord = 0, countTmp = 0;
            for (int k = 0; k < countWordChars.length; ++k) {
                if (countWordChars[k] == 1) countWord++;
                if (countTmpChars[k] == 1) countTmp++;
            }
            return countWord == 1 && countTmp == 1;
        }

        private static void findWordNeighbors(String word, Map<String, List<String>> map, List<String> wordList) {
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; ++i) {
                char originChar = chars[i];
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    if (ch != originChar) {
                        chars[i] = ch;
                        String tmp = String.valueOf(chars);
                        boolean isNeighbor = judgeTwoWordsIsNeighbor(word, tmp, wordList);
                        if (isNeighbor) {
                            List<String> list;
                            if (map.containsKey(word)) {
                                list = map.get(word);
                            } else {
                                list = new ArrayList<>();
                            }
                            list.add(tmp);
                            map.put(word, list);
                        }
                    }
                }
                chars[i] = originChar;
            }
        }
    }

    class Solution1 {

        private int min = Integer.MAX_VALUE;

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            List<List<String>> ans = new ArrayList<>();
            if (!wordList.contains(endWord)) {
                return ans;
            }
            // 得到每个单词相邻的单词
            Map<String, List<String>> map = new LinkedHashMap<>();
            findEachWordNeighbors(beginWord, map, wordList);
            if (map.size() == 0) return ans;
            Set<String> visited = new HashSet<>();
            List<String> list = new ArrayList<>();
            dfs(beginWord, endWord, map, ans, visited, list, 1);
            ans = filter(ans);
            return ans;
        }

        private List<List<String>> filter(List<List<String>> ans) {
            int minSize = Integer.MAX_VALUE;
            for (List<String> list : ans) {
                if (list.size() <= minSize) {
                    minSize = list.size();
                }
            }
            final int finalMinSize = minSize;
            List<List<String>> finalAns = ans.stream().filter(list -> list.size() > finalMinSize ? false : true).collect(Collectors.toList());
            return finalAns;
        }

        private void dfs(String beginWord, String endWord, Map<String, List<String>> map, List<List<String>> ans,

                         Set<String> visited, List<String> list, int step) {
            if (step > min) return;
            if (beginWord.equals(endWord)) {
                list.add(endWord);
                min = Math.min(min, step);
                ans.add(new ArrayList<>(list));
                list.remove(endWord);
                return;
            }
            if (visited.contains(beginWord)) return;
            visited.add(beginWord);
            list.add(beginWord);
            List<String> neighbors = map.get(beginWord);
            if (neighbors != null && neighbors.size() != 0) {
                for (String word : neighbors) {
                    dfs(word, endWord, map, ans, visited, list, step + 1);
                }
            }
            visited.remove(beginWord);
            list.remove(beginWord);
        }

        private void findEachWordNeighbors(String beginWord, Map<String, List<String>> map, List<String> wordList) {
            if (!wordList.contains(beginWord)) {
                findWordNeighbors(beginWord, map, wordList);
            }
            for (String word : wordList) {
                findWordNeighbors(word, map, wordList);
            }
        }

        private boolean judgeTwoWordsIsNeighbor(String word, String tmp, List<String> wordList) {
            if (!wordList.contains(tmp)) return false;
            if (word.length() != tmp.length()) return false;
            int[] countWordChars = new int[26];
            int[] countTmpChars = new int[26];
            for (int i = 0; i < word.length(); ++i) {
                int index1 = word.charAt(i) - 'a';
                countWordChars[index1] += 1;
                int index2 = tmp.charAt(i) - 'a';
                countTmpChars[index2] += 1;
            }
            for (int j = 0; j < countWordChars.length; ++j) {
                if (countWordChars[j] >= countTmpChars[j]) {
                    countWordChars[j] -= countTmpChars[j];
                    countTmpChars[j] = 0;
                } else {
                    countTmpChars[j] -= countWordChars[j];
                    countWordChars[j] = 0;
                }
            }
            int countWord = 0, countTmp = 0;
            for (int k = 0; k < countWordChars.length; ++k) {
                if (countWordChars[k] == 1) countWord++;
                if (countTmpChars[k] == 1) countTmp++;
            }
            return countWord == 1 && countTmp == 1;
        }

        private void findWordNeighbors(String word, Map<String, List<String>> map, List<String> wordList) {
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; ++i) {
                char originChar = chars[i];
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    if (ch != originChar) {
                        chars[i] = ch;
                        String tmp = String.valueOf(chars);
                        boolean isNeighbor = judgeTwoWordsIsNeighbor(word, tmp, wordList);
                        if (isNeighbor) {
                            List<String> list;
                            if (map.containsKey(word)) {
                                list = map.get(word);
                            } else {
                                list = new ArrayList<>();
                            }
                            list.add(tmp);
                            map.put(word, list);
                        }
                    }
                }
                chars[i] = originChar;
            }
        }
    }
}
